Prawie szablon [A]
Limit pamięci: 192 MB
Szablonem słowa nazwiemy takie słowo , że
wszystkie wystąpienia w pokrywają całkowicie słowo
(tzn. każda litera słowa znajduje się wewnątrz jakiegoś
spójnego fragmentu równego ).
Prawie szablonem słowa nazwiemy takie
słowo , że jest podsłowem (tj. spójnym fragmentem) oraz
jest szablonem pewnego nadsłowa słowa . Poniższy rysunek pokazuje,
dlaczego słowo aabaa jest prawie szablonem słowa
aaaabaabaaaba:
Dla danego słowa należy wyznaczyć liczbę jego prawie szablonów oraz
najkrótszy z nich.
Wejście
W jedynym wierszu standardowego wejścia znajduje się niepuste słowo o długości
nie większej niż . Składa się ono z małych liter alfabetu angielskiego.
Wyjście
W pierwszym wierszu standardowego wyjścia należy wypisać liczbę prawie szablonów
słowa . W drugim wierszu należy wypisać najkrótszy prawie szablon słowa .
Jeśli jest więcej niż jeden najkrótszy prawie szablon, to należy wypisać
leksykograficznie najmniejszy spośród najkrótszych prawie szablonów.
Przykład
Dla danych wejściowych:
aaaabaabaaaba
poprawną odpowiedzią jest:
10
aabaa
Podane w przykładowym wejściu słowo ma dziesięć prawie szablonów:
aaaabaabaaab,
aaaabaabaaaba,
aaabaaba,
aaabaabaa,
aaabaabaaa,
aaabaabaaaba,
aabaa,
aabaabaa,
aabaabaaa oraz
abaabaaa.
Autor zadania: Tomasz Idziaszek.